package com.wwlwxg.dataStructure;

import java.io.BufferedWriter;
import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.nio.file.StandardOpenOption;

/**
 * 稀疏数组
 * eg.                                   row     col    value
 * | 0 0 0 0 0 0 0 0 0 0 0 |            | 11     11     2 |
 * | 0 0 1 0 0 0 0 0 0 0 0 |            | 1      2      1 |
 * | 0 0 0 0 2 0 0 0 0 0 0 |            | 2      4      2 |
 * | 0 0 0 0 0 0 0 0 0 0 0 |
 * | 0 0 0 0 0 0 0 0 0 0 0 |
 * | 0 0 0 0 0 0 0 0 0 0 0 |  <=====>
 * | 0 0 0 0 0 0 0 0 0 0 0 |
 * | 0 0 0 0 0 0 0 0 0 0 0 |
 * | 0 0 0 0 0 0 0 0 0 0 0 |
 * | 0 0 0 0 0 0 0 0 0 0 0 |
 * | 0 0 0 0 0 0 0 0 0 0 0 |
 */
public class SparseArray {
	public static void main(String[] args) throws IOException {
		// 创建一个原始的二维数组 11 * 11
		// 0: 表示没有棋子，1表示黑色棋子，2表示蓝色棋子
		int chessArr1[][] = new int[11][11];
		chessArr1[1][2] = 1;
		chessArr1[2][4] = 2;
		// 输出原始的二维数组
		System.out.println("原始的二维数组～～～");
		for(int[] row : chessArr1) {
			for(int data : row) {
				System.out.printf("%d\t", data);
			}
			System.out.println();
		}

		// 将二维数组 转 稀疏数组
		// 1. 先遍历二维数组，得到非0数据的个数
		int count = 0;
		for(int i = 0; i < 11; i++) {
			for(int j = 0; j < 11; j++) {
				if(chessArr1[i][j] != 0) {
					count++;
				}
			}
		}

		// 2. 创建稀疏数组
		int[][] sparseArr = new int[1 + count][3];
		sparseArr[0][0] = 11;
		sparseArr[0][1] = 11;
		sparseArr[0][2] = count;

		// 给稀疏数组赋值
		int index = 1;
		for(int i = 0; i < 11; i++) {
			for(int j = 0; j < 11; j++) {
				if(chessArr1[i][j] != 0) {
					sparseArr[index][0] = i;
					sparseArr[index][1] = j;
					sparseArr[index][2] = chessArr1[i][j];
					index++;
				}
			}
		}

		// 输出稀疏数组的形式
		System.out.println("对应的稀疏数组为： ");
		for(int i = 0; i < sparseArr.length; i++) {
			System.out.printf("%d\t%d\t%d\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
		}

		// 将稀疏数组恢复为原始数组
		int[][] cherryArr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
		for(int i = 1; i <= sparseArr[0][2]; i++) {
			cherryArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
		}

		// 打印恢复的原始数组
		System.out.println("恢复的原始的二维数组～～～");
		for(int[] row : cherryArr2) {
			for(int data : row) {
				System.out.printf("%d\t", data);
			}
			System.out.println();
		}

		if(Files.notExists(Paths.get("a.txt"))) {
			Files.createFile(Paths.get("a.txt"));
		}
		try(BufferedWriter writer = Files.newBufferedWriter(Paths.get("a.txt"), new StandardOpenOption[]{ StandardOpenOption.WRITE})) {
			for(int i = 0; i < sparseArr.length; i++) {
				writer.write(sparseArr[i][0] + "");
				writer.write(",");
				writer.write(sparseArr[i][1] + "");
				writer.write(",");
				writer.write(sparseArr[i][2] + "");
				writer.newLine();
			}
			writer.flush();
		}

	}
}
